using System;
using System.Collections.Generic;

namespace Dida
{
	public static class DependencySorter
	{
		public interface IItem : IComparable<IItem>, IComparable
		{
			IList<IItem> Dependencies
			{
				get;
			}
		}

		public class CircularReferenceException : Exception
		{
		}

		private static List<IItem> DoSorting(List<IItem> unsorted)
		{
			List<IItem> sortedList = new List<IItem>();
			SortedSet<IItem> sortedItems = new SortedSet<IItem>();			
			foreach (IItem cur in unsorted)
			{
				if (!sortedItems.Contains(cur))
				{
					List<IItem> depending = new List<IItem>();
					SortDependencyTree(cur, depending, sortedList, sortedItems);
				}
			}

			return sortedList;
		}

		private static void SortDependencyTree(IItem item,List<IItem> depending,
			List<IItem> sortedList,SortedSet<IItem> sortedItems)
		{
			depending.Add(item);
			foreach (IItem dep in item.Dependencies)
			{
				if (!sortedItems.Contains(dep))
				{
					// check for circular references
					foreach (IItem dependingObj in depending)
					{
						if (dependingObj == dep)
						{
							// we found a circular reference
							throw new CircularReferenceException();
						}
					}

					SortDependencyTree(dep, depending, sortedList,sortedItems);
				}
			}
			depending.RemoveAt(depending.Count - 1);

			sortedList.Add(item);
			sortedItems.Add(item);			
		}

		public static List<T> SortDependencies<T>(List<T> unsorted)
			where T : IItem
		{
			List<IItem> unsortedList = new List<IItem>();
			unsortedList.Capacity = unsorted.Count;
			foreach (T cur in unsorted)
				unsortedList.Add(cur);

			List<IItem> res = DoSorting(unsortedList);
			
			List<T> resList = new List<T>();
			resList.Capacity = unsorted.Count;
			foreach (IItem cur in res)
				resList.Add((T)cur);

			return resList;
		}
	}
}